// Allocator that wraps "C" posix_memalign -*- C++ -*-

// Modified 2007 by F.P.Beekhof

// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/** @file base/Allocators
 *  Allocators.
 */

#ifndef CVMLCPP_ALLOCATORS
#define CVMLCPP_ALLOCATORS 1

#include <errno.h>

#include <limits>

#include <cstdlib>
#include <new>
// #include <bits/functexcept.h>
// #include <except>

#include <boost/integer/static_log2.hpp>
#include "../math/Math"

namespace cvmlcpp
{

  /**
   *  @brief  An allocator that uses posix_memalign.
   *
   *  Modeled after the allocator defined in the C++ Standard.
   *    - all allocation calls posix_memalign
   *    - all deallocation calls free
   */
template<typename _Tp, std::size_t N = 4u>
class AlignAllocator
{
	public:
		typedef std::size_t	size_type;
		typedef std::ptrdiff_t	difference_type;
		typedef _Tp*       	pointer;
		typedef const _Tp* 	const_pointer;
		typedef _Tp&       	reference;
		typedef const _Tp& 	const_reference;
		typedef _Tp        	value_type;

		template<typename _Tp1>
		struct rebind
		{ typedef AlignAllocator<_Tp1, N> other; };

		AlignAllocator() throw() { }

		AlignAllocator(const AlignAllocator&) throw() { }

		template<typename _Tp1>
		AlignAllocator(const AlignAllocator<_Tp1, N>&) throw() { }

		~AlignAllocator() throw() { }

		pointer
		address(reference __x) const { return &__x; }

		const_pointer
		address(const_reference __x) const { return &__x; }

		// NB: __n is permitted to be 0.  The C++ standard says nothing
		// about what the return value is when __n == 0.
		pointer
		allocate(size_type __n, const void* = 0) throw (std::bad_alloc)
		{
			if (__n > this->max_size())
 				throw std::bad_alloc();

			void *__ret = 0;

			const std::size_t min_size = 16;

			const std::size_t twoPwN = 1u <<
				boost::static_log2<N*sizeof(_Tp)>::value;

			const std::size_t align = std::max(min_size,
				(twoPwN==(N*sizeof(_Tp))) ? twoPwN:(2u*twoPwN));

			assert(align >= (N*sizeof(_Tp)));
			assert(isPower2(align));
			const int pm_ret =
			    posix_memalign0(&__ret, align, __n * sizeof(_Tp));
			assert(pm_ret != EINVAL);

			if (pm_ret != 0)
			{
				assert(pm_ret == ENOMEM);
 				throw std::bad_alloc();
			}
			return static_cast<pointer>(__ret);
		}

		// __p is not permitted to be a null pointer.
		void
		deallocate(pointer __p, size_type)
		{ free0(static_cast<void*>(__p)); }

		size_type
		max_size() const throw()
		{ return std::numeric_limits<size_t>::max() / sizeof(_Tp); }

		// _GLIBCXX_RESOLVE_LIB_DEFECTS
		// 402. wrong new expression in [some_] allocator::construct
		void
		construct(pointer __p, const _Tp& __val)
		{ ::new(__p) value_type(__val); }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
		template<typename... _Args>
		void construct(pointer __p, _Args&&... __args)
		{ ::new((void *)__p) _Tp(std::forward<_Args>(__args)...); }
#endif

		void destroy(pointer __p) { __p->~_Tp(); }

	private:
		int posix_memalign0(void **memptr,
				    const size_t alignment, const size_t size)
		{
#if _XOPEN_SOURCE >= 600
			return posix_memalign(memptr, alignment, size);
#else
			if ( (alignment % sizeof (void *) != 0) ||
			     ((alignment & (alignment - 1)) != 0) )
				return EINVAL;

			void *p0=malloc(size+alignment);
			if(!p0) return ENOMEM;
			void *p= reinterpret_cast<void *>
				(((size_t)p0+alignment)&~(alignment-1));
			*((void **) p-1)=p0;
			*memptr=p;
			return 0;
#endif
		}

		void free0(void *p)
		{
#if _XOPEN_SOURCE >= 600
			free(p);
#else
			if(p) free(*((void **) p-1));
#endif
		}

};

template<typename _Tp, std::size_t N>
inline bool
operator==(const AlignAllocator<_Tp, N>&, const AlignAllocator<_Tp, N>&)
{ return true; }

template<typename _Tp, std::size_t N>
inline bool
operator!=(const AlignAllocator<_Tp, N>&, const AlignAllocator<_Tp, N>&)
{ return false; }

} // namespace

#endif
